/*
Date:20210417 16:39pm
key:左缩右缩只存在两种情况，而且相差一个的时候就可以判断了
    以上是寻找可重复最小值下标的办法，复杂度O(logn).
    那么找到最小下标就相当于划分出两个递增数组。
    分别在这两个数组上二分查找即可。整体复杂度仍是O(logn)先找到最小指。
    [first, last) 区域内查找不小于 val 的元素：lower_bound。
    如果要查的在后面一段递增，那么在前一段递增第一个就比它大会停下来，因此要把下标放回去验证本体才行。
*/
class Solution {
public:
    int erfen(int L,int R,vector<int>& nums)
    {
        //相差一个的时候就可以判断了
        if(L+1>=R)
        {
            return nums[L]>nums[R]?R:L;
        }
        else
        {
            
            //int key=nums[ceil((double)(L+R)/2)];
            int key=nums[(L+R)/2];
            //cout<<key;
            if(nums[L]<=key&&nums[L]>nums[R])
            {
                //cout<<"右";
                return erfen((L+R)/2,R,nums);
            }
            if(nums[L]>key&&key<=nums[R])
            {
                //cout<<"左";
                return erfen(L,(L+R)/2,nums);
            }
            //这里一定要有return key，我也不知道为什么
            return (L+R)/2;
        }
    }
    int search(vector<int>& nums,int target)
     {
        if(nums.size()==0)
        {
            return 0;
        }
        if(nums.size()==1)
        {
            if(nums[0]==target)
            {
return 0;
            }
            else
            {
return -1;
            }
           
        }
        
        //如果数组单调递增
        if(nums[0]<nums[nums.size()-1])
        {
            auto k=lower_bound(nums.begin(),nums.end(),target);
            if(k!=nums.end()&&nums[k-nums.begin()]==target)
            {
                return k-nums.begin();
            }
            else return -1;
            
        }
        else
        {
            //先找到最小指。
            
            int i=erfen(0,nums.size()-1,nums);
             cout<<i;
            auto k=lower_bound(nums.begin(),nums.begin()+i,target);
            
            if(k!=nums.begin()+i&&nums[k-nums.begin()]==target) return k-nums.begin();
            k=lower_bound(nums.begin()+i,nums.end(),target);
            //cout<< k-nums.begin();
            if(k!=nums.end()&&nums[k-nums.begin()]==target) return k-nums.begin();else{return -1;}
        }
    }
};